package net.guruqu.cds;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;
import java.util.Vector;

public class RandomGraphGenerater {
	static Random random = new Random(123);
	
	
	public static Vector<int[]> generateEdges(int nodes,int edges){
		Vector<int[]> output = new Vector<int[]>();
		HashMap<Integer,HashSet<Integer>> graph = new HashMap<Integer, HashSet<Integer>>();
		int edgeCount=0;
		for(int i=0;i<nodes;i++){
			graph.put(i,new HashSet<Integer>());
		}
		while(edgeCount<edges){
			int na,nb;
			na = random.nextInt(nodes);
			nb = random.nextInt(nodes);
			if(na==nb)
				continue;
			if(graph.get(na).contains(nb))
				continue;
			edgeCount++;
			
			HashSet<Integer> ea = graph.get(na);
			ea.add(nb);
			

			HashSet<Integer> eb = graph.get(nb);
			eb.add(na);
			
			output.add(new int[]{na,nb});
		}
		
		boolean visited[] = new boolean[nodes];
		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.add(0);
		int visiteCount=0;
		while(visiteCount!=nodes){
			int last=-1;
			while(!queue.isEmpty()){
				Integer cur=queue.removeLast();
				if(visited[cur])
					continue;
				visited[cur]=true;
				visiteCount++;
				for(Integer nb : graph.get(cur))
					queue.addFirst(nb);
				last = cur;
			}
			for(int i=0;i<nodes;i++){
				if(!visited[i]){
					queue.add(i);
					graph.get(i).add(last);
					graph.get(last).add(i);
					
					output.add(new int[]{i,last});
//					System.out.println("add connect edge-"+i+","+last);
					break;
				}
			}
		}
		return output;
	}
	
	public static void main(String s[]){
		Vector<int[]> edges = generateEdges(10, 20);
		for(int[] i : edges){
			System.out.println(i[0]+"-"+i[1]);
		}
	}
}
